Switch level simulation of digital circuits is an important design verification tool for designers of MOS integrated circuits. However, switch level simulation software running on a general purpose computer can take days to accomplish an exhaustive simulation on a large circuit of about 100,000 transistor devices. As the complexity of VLSI circuits increases, the time and cost to perform a complete software simulation on a general purpose computer is becoming prohibitive. One approach being developed is the construction of hardware specifically designed to handle switch level simulation of MOS transistor circuits. Performance factors which are important include not only speed, but also capacity to load and process large netlists corresponding to realistic LSI/VLSI circuit designs, timing analysis capability in addition to unit delay simulation, the ability to handle commonly used circuit design techniques, such as steering or pass transistor logic, and accuracy. The hardware simulator must be based on an algorithm that is sufficiently accurate to be useful, yet not so complex as to be unable to be put into hardware.
In IEEE Transaction of Computers, vol. C-33, no. 2, February, 1984, pp. 160-177, Bryant describes a switch level model that has been developed to describe the logical behavior of MOS transistor circuits, and then describes an algorithm for a logic simulator based on the model. A hardware architecture for implementing this algorithm is described by Dally and Bryant in IEEE Transactions on Computer-Aided Design, vol. CAD-4, no. 3, July, 1985, pp. 239-250.
In the model a network consists of a set of nodes connected by transistor switches. Each node has a state 0, 1 or X representing low, high and invalid voltages. Likewise, each transistor has a state 0, 1 or X representing open (nonconducting or OFF) closed (conducting or ON) and indeterminate conditions. Input nodes, including power and ground nodes, as well as any clock or data inputs, provide signals to the system and are not affected by the actions of the network. Storage nodes have states determined by the operation of the network, and these states remain on the nodes in the absence of applied inputs. Each storage node is assigned one of a number of discrete size values K.sub.1, . . . , K.sub.max that indicates its approximate capacitances in relation to other nodes. Each transistor has a strength .gamma..sub.1, . . . , .gamma..sub.max, indicating its conductance when closed relative to other transistors which may form part of a ratioed path.
The algorithm simulates the behavior of a circuit by taking a series of unit steps, where within each step the new excitation states of the nodes, i.e. the steady-state response of the nodes for an initial set of nodes states when the transistors are held fixed in states determined by the states of their gate nodes, are computed and the nodes are updated to their new states. This is done repeatedly until either a stable state is reached or a user defined step limit is exceeded. Determining the new excitation states is a four step process comprising a "logic update" step, a "perturbation" step, a "blocking strength" step and a "up/down" step. During the "logic update" step, the conduction states of the transistors whose gate nodes have changed state in the last node update are updated, and the source and drain nodes of these transistors are queued for the next step. During the "perturbation" step, the set of all nodes that could be affected by the changing transistor states are found by starting at the nodes queued in the logic update step and traversing the links representing transistors in the 1 or X state. Each time a new node is encountered, it is added to the queue. The "blocking strength" step determines the strength of the strongest definite path to each node in the queue, a path being definite if none of its edges correspond to transistors in the X state, and the strength of a path being defined as the minimum of the size of the root node and the strengths of the transistors corresponding to the path edges, where strength values are ordered K.sub.1, &lt; . . . &lt;K.sub.max &lt;.gamma..sub.1 &lt; . . . &lt;.gamma..sub.max &lt;.omega.. The "up/down strength" step computes the up (respectively, down) value for each node, i.e. the strength of the strongest unblocked path to the node having a root node with state 1 or X (respectively, 0 or X). If no such path exists, the value is set to 0. Once this computation terminates the steady-state response of the node equals 1 if the down value equals 0, 0 if the up value equals 0, and X otherwise. This algorithm just described will henceforth be called the "Bryant algebra".
The Bryant algebra and the Dally and Bryant hardware architecture which implements the algebra does not deal with MOS circuits employing pass transistors. In that architecture an enhancement device is considered to be ON if the gate has the correct logic level, even if the gate and source are shorted. In this case, the gate to source voltage V.sub.gs would be zero and would be less than a positive threshold voltage V.sub.th. Thus, the transistor would in fact be OFF.
A limitation of other prior art simulators is that they are adapted to perform only in a unit delay mode and thus cannot do timing analysis. In some circuits, a proper prediction of behavior requires delay times to be taken into account.
In IEEE Transactions on Computer-Aided Design, vol. CAD-3, no. 4, October, 1984, pp. 331-349, Lin and Mead disclose a method for determining a single value of Elmore's delay for any node changing state in a general RC network. The effects of parallel connections and initial stored charges on nodes are taken into consideration. A simulation algorithm based on Bryant's algebra is described.
In Proceedings of the IEEE International Conference on Computer Design 1985, pp. 586-589, Smith discloses a simulation algorithm which accurately predicts the behavior of MOS transistor circuits including pass transistors. Smith modifies the "up/down strength" step of the Bryant algebra for MOS transistor circuits including pass transistors to determine if there is an unblocked path between gate and source node of a transistor.
It is an object of the present invention to produce a hardware switch level simulator for MOS transistor circuits which is able to accurately simulate the behavior of circuits using pass transistors.
It is another object of the invention to produce such a hardware simulator which is also fast, has the capacity to handle realistic VLSI circuit designs, and offers the option of performing timing analysis in addition to unit delay simulation.